package org.example.dp;
//https://leetcode.cn/problems/longest-increasing-subsequence/
import java.util.Arrays;
//300. 最长递增子序列
class Solution {
    //动态规划
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = 0; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int max = 0;
        for(int x : dp) max = Math.max(max, x);
        return max;
    }
}